#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x) {next = NULL;}
};

class Solution
{
public:
    ListNode* sortList(ListNode *head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode *mid = head, *tail = head;
        while(tail != NULL && tail->next !=NULL && tail->next->next!=NULL) {
            mid = mid->next;
            tail = tail->next->next;
        }

        ListNode *p = mid->next;
        mid->next = NULL;
        head = sortList(head);
        p = sortList(p);
        return combine(head,p);
    }
private:
    ListNode* combine(ListNode *p, ListNode *q) {
        ListNode *head;
        ListNode **pList = &head;
        while(p!=NULL && q!=NULL) {
            if (p->val < q->val) {
                *pList = p;
                p = p->next;
            } else {
                *pList = q;
                q = q->next;
            }
            pList = &((*pList)->next);
        }
        if(p!=NULL) *pList = p;
        if(q!=NULL) *pList = q;
        return head;
    }
};
void print(ListNode *head) {
    while(head!=NULL) {
        cout <<head->val<<" ";
        head = head->next;
    }
    cout <<endl;
}
int main(int argc, char *argv[])
{
    ListNode *head = new ListNode(12);
    ListNode *p = head;
    int a[] = {6,1,3,78,32,2,90,123,345};
    for (int i = 0; i < sizeof(a)/sizeof(int); ++i) {
        p->next = new ListNode(a[i]);
        p = p->next;
        p->next = NULL;
    }
    Solution ss;
    print(head);
    head = ss.sortList(head);
    print(head);
    return 0;
}
